import java.util.PriorityQueue;

public class FindUnsortedSubarray {

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 34, 756, 453, 89};
        System.out.println(new FindUnsortedSubarray().findUnsortedSubarray(nums));
    }

    public int findUnsortedSubarray1(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        PriorityQueue<Integer> heapMax = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> heapMin = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            heapMax.add(nums[i]);
            heapMin.add(nums[i]);
        }
        while (l < r && (heapMax.peek() == nums[r] || heapMin.peek() == nums[l])) {
            if (heapMax.peek() == nums[r]) {
                heapMax.poll();
                --r;
            }
            if (heapMin.peek() == nums[l]) {
                heapMin.poll();
                ++l;
            }
        }
        return r == l ? 0 : r - l + 1;
    }

    public int findUnsortedSubarray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int l = -1;
        int r = -1;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] < max) {
                l = i;
            } else max = nums[i];
            if (nums[n - 1 - i] > min) {
                r = n - 1 - i;
            } else min = nums[n - 1 - i];
        }
        return l == -1 ? 0 : l - r + 1;
    }
}
